package com.frx.sort.mergesort;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/10/22
 * @Time: 17:05
 */
public class TestOne {

    public static void main(String[] args){
        int[] arr = {2,7,3,9,8,4,1};
        mergeSort(arr,0,arr.length -1);
        System.out.println(Arrays.toString(arr));
    }


    public static void mergeSort(int[] arr,int start,int end){
        if (start < end){
            /*int mid = start + (end-start) >> 1;*/
            int mid = start + ((end - start)>>1);
            System.out.println("mid = " + mid);

            mergeSort(arr,start,mid);
            mergeSort(arr,mid+1,end);
            merge(arr,start,mid,end);
        }

    }
    private static void merge(int[] arr,int start,int mid,int end){
        int[] tempArr = new int[end-start+1];
        int p = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end){
            if (arr[p1] < arr[p2]){
                tempArr[p++] = arr[p1++];
            } else {
                tempArr[p++] = arr[p2++];
            }
        }
        while (p1 <= mid){
            tempArr[p++] = arr[p1++];
        }
        while (p2 <= end){
            tempArr[p++] = arr[p2++];
        }

        for (int i = 0; i< tempArr.length;i++){
            arr[i+start] = tempArr[i];
        }
    }

}
